package com.javatest;

import java.util.Scanner;

/**
 * @author LL
 *题目：输入两个正整数m和n，求其最大公约数和最小公倍数。
 * @create 2020-12-10 9:55
 */
public class Subject06 {

    //递归求公约数
    public static int maxCommonDivisor(int m, int n) {
        if (m < n) {// 保证m>n,若m<n,则进行数据交换
            int temp = m;
            m = n;
            n = temp;
        }
        if (m % n == 0) {// 若余数为0,返回最大公约数
            return n;
        } else { // 否则,进行递归,把n赋给m,把余数赋给n
            return maxCommonDivisor(n, m % n);
        }
        /**
         * (1)充分性：
         * 设g是a,b的公约数，则a,b可由g来表示：
         * a = xg, b = yg (x,y为整数)
         * 又，a可由b表示（任意一个数都可以由另一个数来表示）：
         * a = kb + r (k为整数，r为a除以b所得余数)
         * => r = a - kb = xg - kyg = (x - ky)g
         * 即，g也是r的约数。
         * 这样，g就是(b, r)即(b, a mod b)的公约数
         */
    }

    public static int gcd(int p, int q){
        //欧几里得算法，最大公约数
        if (q == 0) return p;
        int r = p % q;
        return gcd(q, r);
        //return q == 0?p:gcd(p,r);
    }

    //公约数
    public static int divisor(int a,int b){
        int result = 1;
        int tmp = a>b?b:a;
        for (int i = 2; i <= tmp; i++) {
            if (a%i == 0 && b%i == 0){
                result = i*result;
                a = a/i;
                b = b/i;
                i = 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        try {
            System.out.println("输入第一个正整数：");
            int i = sc.nextInt();
            System.out.println("输入第二个正整数：");
            int i1 = sc.nextInt();
            int divisor = divisor(i, i1);
            System.out.println("最大公约数："+divisor);
            int multiple = (i*i1)/divisor;
            System.out.println("最小公倍数："+multiple);
            //maxCommonDivisor(i,i1);
            gcd(i,i1);
        }catch (Exception e){
            System.out.println("输入数字不正确！"+e);
        }
    }
}
